package zachary.hackerson.ds;

import algrs.jar.Queue;
import algrs.jar.Stack;

public class BreathFirstPath {

	public boolean[] marked;
	public int s;
	public int[] edgeTo;
	public Graph G;
	public BreathFirstPath(Graph g, int V) {
		this.s = V;
		this.G = g;
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		bfs(this.s);
	}
	
	private void bfs(int s2) {
		Queue<Integer> queue = new Queue<Integer>();
		marked[s2] = true;
		queue.enqueue(s2);
		while(!queue.isEmpty()) {
			int v = queue.dequeue();
			for(int w: G.adj(v)) {
				if(!marked[w]) {
					queue.enqueue(w);
					marked[w] = true;
					edgeTo[w] = v;
				}
			}
		}
	}

	public boolean hashPathTo(int w) {
		return marked[w];
	}
	public Iterable<Integer> path(int w) {
		if(!hashPathTo(w)) return null;
		Stack<Integer> stack = new Stack<Integer>();
		for(int i = w; i != s; i = edgeTo[i]) 
			stack.push(i);
		stack.push(s);
		return stack;
	}
	public static void main(String[] args) {

	}

}
